package Algorithm.backTracking;

import java.util.*;

/**
 * 47. 全排列 II https://leetcode.cn/problems/permutations-ii/
 * 题目简述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class PermuteUnique {

    public static void main(String[] args) {
        new PermuteUnique().permuteUnique(new int[]{1,1,2});
    }

    /**
     * 思路：回溯算法。由于有重复元素，故先对数组排序，然后在同层路径选择时去重，对于同层选择列表中的重复元素，只有未使用的重复元素中的第一个可以使用，
     * 后面的在同层中都重复了，由于是按顺序扫描，故对重复元素的使用是按顺序来的，因此前半部分是已使用，后半部分是未使用，
     * 故当元素和前一个重复时，只有当前一个使用过了，它才是未使用部分的第一个，故需对i > 0 && nums[i] == nums[i-1] && !used[i-1]进行剪枝以去除同层重复。
     *
     * 回溯递归函数参数：（结果集，已选择路径，数组nums和已使用标记used构成的下一步路径选择列表）
     * 回溯递归函数体：1.路径长度已达到要求，则加入结果集然后return
     *              2.遍历当前选择列表：同层去重。将选择加入路径，然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择
     * 同层选择列表去重：连续相同元素的情况下，只有在上一个是上一层使用过的，这一层才可以用这一个，否则同层就重复了
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        //要保留路径顺序，不能用HashSet
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[nums.length];
        backTracking(result, path, nums, used);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, boolean[] used) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        //路径选择列表：[0, n-1]
        for(int i=0;i < nums.length;i++) {
            //可行性剪枝：已使用数据略过
            if (!used[i]) {
                //可行性剪枝：同层选择列表去重：若nums[i]与上一个元素值相同且上一个元素没有使用过，则略过nums[i]
                //意思就是说连续相同元素的情况下，只有在上一个重复的是前面层使用过的，这一层才可以用这一个，否则同层就重复了
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1])
                    continue;
                path.add(nums[i]);
                used[i] = true;
                backTracking(result, path, nums, used);
                path.removeLast();
                used[i] = false;
            }
        }
    }
}
